package com.acwing.chapter3.dui;

import java.io.*;

/**
 * @author anan
 * @create 2021-08-27 21:11
 */
public class Dui839 {
    private static int N = 100010;
    private static int[] h = new int[N];
    private static int[] ph = new int[N];
    private static int[] hp = new int[N];
    private static int size, m;

    private static void swap(int[] arr ,int a, int b){
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }

    private static void heapSwap(int a, int b){
        swap(h, a, b);
        swap(ph, hp[a], hp[b]);
        swap(hp, a, b);
    }

    private static void down(int u){
        int t = u;
        if (2*u <= size && h[2*u] < h[u]) t = 2*u;
        if (2*u + 1 <= size && h[2*u + 1] < h[t]) t = 2*u + 1;
        if (t != u) {
            heapSwap(t, u);
            down(t);
        }
    }

    private static void up(int u){
        while (u/2 > 0 && h[u/2] > h[u]){
            heapSwap(u/2, u);
            u = u/2;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] str1 = reader.readLine().split(" ");
        int n = Integer.parseInt(str1[0]);
        while (n-- > 0){
            String[] str2 = reader.readLine().split(" ");
            if ("I".equals(str2[0])){
                h[++size] = Integer.parseInt(str2[1]);
                ph[++m] = size;
                hp[size] = m;
                up(size);
            }

            if ("PM".equals(str2[0])) writer.write(h[1] + "\n");

            if ("DM".equals(str2[0])){
                heapSwap(1, size);
                size--;
                down(1);
            }

            if ("D".equals(str2[0])){
                int k = Integer.parseInt(str2[1]);
                k = ph[k];
                heapSwap(k, size);
                size--;
                up(k);
                down(k);
            }

            if ("C".equals(str2[0])){
                int k = Integer.parseInt(str2[1]);
                int x = Integer.parseInt(str2[2]);
                k = ph[k];
                h[k] = x;
                up(k);
                down(k);
            }

        }
        writer.flush();
        writer.close();
        reader.close();
    }

}















